The present invention generally relates to electronic circuit design. More particularly, the present invention is directed to efficiently and accurately finding predetermined patterns in a main circuit design.
Recognizing or finding subcircuit instances in a larger circuit is widely used in the simulation, verification, and testing of integrated circuits using computer-aided design programs. Currently, the process of finding is performed using ad hoc techniques that rely on the circuit technology and implementation details. Such techniques, however, do not generalize to different subcircuit structures and do not transfer to other technologies. A publication entitled “SubGemini: Identifying SubCircuits using a Fast subgraph Isomorphism Algorithm,” by Ohlrich, et. al. (hereinafter “SubGemini”) describes a technology independent algorithm for solving this problem based on a solution to the subgraph isomorphism problem. This publication is incorporated herein by reference. SubGemini describes a use of a recursive relabeling approach to identify circuit patterns in a larger circuit. However, the SubGemini method of finding patterns in a larger circuit has flaws that, under certain circumstances, prevent the labels from having enough information to ensure an accurate identification of the instances of the subcircuits in larger circuits.
Thus, there is a need for method and system that enable a more accurate and efficient identification of patterns (i.e., subcircuits) in a larger circuit.